//Given an array of integers nums sorted in ascending order, find the starting a
//nd ending position of a given target value. 
//
// If target is not found in the array, return [-1, -1]. 
//
// You must write an algorithm with O(log n) runtime complexity. 
//
// 
// Example 1: 
// Input: nums = [5,7,7,8,8,10], target = 8
//Output: [3,4]
// Example 2: 
// Input: nums = [5,7,7,8,8,10], target = 6
//Output: [-1,-1]
// Example 3: 
// Input: nums = [], target = 0
//Output: [-1,-1]
// 
// 
// Constraints: 
//
// 
// 0 <= nums.length <= 105 
// -109 <= nums[i] <= 109 
// nums is a non-decreasing array. 
// -109 <= target <= 109 
// 
// Related Topics 数组 二分查找 
// 👍 1009 👎 0


package leetcode.editor.cn;

//Java：Find First and Last Position of Element in Sorted Array
class P34FindFirstAndLastPositionOfElementInSortedArray {
    public static void main(String[] args) {
        Solution solution = new P34FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        // TO TEST
        solution.searchRange(new int[]{2, 2}, 3);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {

            int[] result = new int[2];
            result[0] = -1;
            result[1] = -1;
            if (nums == null || nums.length == 0) {
                return result;
            }
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                int midVal = nums[mid];
                if (midVal >= target) {
                    right = mid - 1;
                } else if (midVal < target) {
                    left = mid + 1;
                }
            }
            result[0] = left;
            if (left > nums.length - 1 || nums[left] != target) {
                result[0] = -1;
                return result;
            } else if (left == nums.length - 1) {
                if (nums[left] == target) {
                    result[0] = left;
                    result[1] = left;
                    return result;
                }
            }
            right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                int midVal = nums[mid];
                if (midVal > target) {
                    right = mid - 1;
                } else if (midVal <= target) {
                    left = mid + 1;
                }
            }
            result[1] = left - 1;
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}